﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0039_CheckInclusion : IAlgorithm
    {
        // 567. 字符串的排列

        // 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

        // 换句话说，s1 的排列之一是 s2 的 子串 。（注意此处为's1的排列之一'）

        // 提示：
        //  1 <= s1.length, s2.length <= 10^4
        //  s1 和 s2 仅包含小写字母

        public void Test()
        {
            // 算法参数定义
            string s1 = "ab", s2 = "eidbaoo";
            // 算法执行与打印
            Console.WriteLine(CheckInclusion(s1, s2));
        }

        // 算法
        // 移动窗口
        public bool CheckInclusion(string s1, string s2)
        {
            if (s1.Length > s2.Length)
                return false;
            var charCount = new int[26];
            for (int i = 0; i < s1.Length; i++)
            {
                charCount[s1[i] - 'a']--;
                charCount[s2[i] - 'a']++;
            }
            int diff = 0;
            foreach (var item in charCount)
                if (item != 0)
                    diff++;
            if (diff == 0)
                return true;
            for (int i = s1.Length; i < s2.Length; i++)
            {
                // x进入窗口的字符，y出窗口的字符
                int x = s2[i] - 'a', y = s2[i - s1.Length] - 'a';
                // 两值相等继续循环
                if (x == y)
                    continue;
                // 若进入窗口字符已平衡，进入会导致偏差
                if (charCount[x] == 0)
                    diff++;
                // 记录进入字符
                charCount[x]++;
                // 进入后平衡，偏差减一
                if (charCount[x] == 0)
                    diff--;
                // 出窗口字符原为平衡状态，出窗口会增加偏差
                if (charCount[y] == 0)
                    diff++;
                // 记录出窗口字符
                charCount[y]--;
                // 若出窗口后平衡，偏差减小
                if (charCount[y] == 0)
                    diff--;
                // 偏差为0，全部平衡，s1的排列之一为s2的子串
                if (diff == 0)
                    return true;
            }
            return false;
        }

        // 双指针,类似
        public bool CheckInclusion1(string s1, string s2)
        {
            int n = s1.Length, m = s2.Length;
            if (n > m)
                return false;
            int[] cnt = new int[26];
            for (int i = 0; i < n; ++i)
            {
                --cnt[s1[i] - 'a'];
            }
            int left = 0;
            for (int right = 0; right < m; ++right)
            {
                int x = s2[right] - 'a';
                ++cnt[x];
                while (cnt[x] > 0)
                {
                    --cnt[s2[left] - 'a'];
                    ++left;
                }
                if (right - left + 1 == n)
                {
                    return true;
                }
            }
            return false;
        }
    }
}
